// 复制带随机指针的链表
// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/
public class CopyListWithRandomPointer {
    public static class Node {
        public int val;
        public Node next;
        public Node random;

        public Node(int v) {
            val = v;
        }
    }

    public static Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }
        Node cur = head, next = null;

        Node copyNode;
        while (cur != null) {
            next = cur.next;
            copyNode = new Node(cur.val);  //创建新结点
            //链接上新结点
            cur.next = copyNode;
            copyNode.next = next;

            cur = next;
        }

        cur = head;
        //链接新结点的随机结点
        while (cur != null) {
            copyNode = cur.next;

            if(cur.random == null) {
                copyNode.random = null;
            } else {
                copyNode.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        //分离出新链表
        cur = head;
        copyNode = head.next;


        Node ans = copyNode;
        while(cur != null) {
            Node curNext = copyNode.next;
            if(curNext == null) {
                break;
            }
            Node copyNext = curNext.next;

            cur.next = curNext;
            copyNode.next = copyNext;

            cur = curNext;
            copyNode = copyNext;
        }
        cur.next = null;
        return ans;
    }
}
